{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find The K-th Lucky Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthLuckyNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出第 K 个幸运数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们知道 <code>4</code> 和 <code>7</code> 是 <strong>幸运</strong> 数字。同时，如果一个数字只包含幸运数字，那么它被称为幸运数字。</p>\n",
    "\n",
    "<p>给定一个整数 <code>k</code>，返回第 <code>k</code> 个幸运数字，并将其表示为一个 <strong>字符串</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 4\n",
    "<b>输出：</b>\"47\"\n",
    "<b>解释：</b>第一个幸运数字是 4，第二个是 7，第三个是 44，第四个是 47。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>k = 10\n",
    "<b>输出：</b>\"477\"\n",
    "<b>解释：</b>按递增顺序列出的幸运数字为：\n",
    "4, 7, 44, 47, 74, 77, 444, 447, 474, 477。 因此第10个幸运数字是477。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>k = 1000\n",
    "<b>输出：</b>\"777747447\"\n",
    "<b>解释：</b>第 1000 个幸运数字是 777747447。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-k-th-lucky-number](https://leetcode.cn/problems/find-the-k-th-lucky-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-k-th-lucky-number](https://leetcode.cn/problems/find-the-k-th-lucky-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '10', '1000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber1(self, k: int) -> str:\n",
    "        return ''.join(['4' if c=='0' else '7' for c in bin(k+1)[3:]])\n",
    "        \n",
    "    \n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        srt, sm, p = 1, 2, 4\n",
    "        while k > sm:\n",
    "            sm += p\n",
    "            srt += 1\n",
    "            p *= 2\n",
    "        s = bin(k-1-sm+p//2)[2:].rjust(srt,\"0\")\n",
    "        return s.replace(\"0\",\"4\").replace(\"1\",\"7\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return bin(k+1)[2:].replace('0','4').replace('1','7')[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return bin(k+1)[3:].replace('0', '4').replace('1', '7')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return bin(k+1)[3:].replace('0', '4').replace('1','7')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        tmp1=1\n",
    "        while k>2**tmp1:\n",
    "            k-=2**tmp1\n",
    "            tmp1+=1\n",
    "        tmp2=bin(k-1)[2:]\n",
    "        res=''\n",
    "        for i in tmp2:\n",
    "            if i==\"1\":\n",
    "                res+='7'\n",
    "            else:\n",
    "                res+=\"4\"\n",
    "        res=\"4\"*(tmp1-len(tmp2))+res\n",
    "        return res\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        result = ''\n",
    "        while k:\n",
    "            result = '74'[k & 1] + result\n",
    "            k = k - 1 >> 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return bin(k+1-2**(srt:=int(math.log(k+1,2))))[2:].rjust(srt,\"0\").replace(\"0\",\"4\").replace(\"1\",\"7\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        k += 1\n",
    "        a = bin(k)\n",
    "        ans = ''\n",
    "        for ch in a[3:]:\n",
    "            if ch == '0':\n",
    "                ans += '4'\n",
    "            else:\n",
    "                ans += '7'\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return bin(k+1)[3:].replace(\"0\",\"4\").replace(\"1\",\"7\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return bin(k+1)[3:].replace(\"0\",\"4\").replace(\"1\",\"7\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        return ''.join(['4' if c=='0' else '7' for c in bin(k+1)[3:]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        srt, sm, p = 1, 2, 4\n",
    "        while k > sm:\n",
    "            sm += p\n",
    "            srt += 1\n",
    "            p *= 2\n",
    "        s = bin(k-1-sm+p//2)[2:].rjust(srt,\"0\")\n",
    "        return s.replace(\"0\",\"4\").replace(\"1\",\"7\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        for ln in count(1):\n",
    "            if k > 2 ** ln:\n",
    "                k -= 2 ** ln\n",
    "            else:\n",
    "                break\n",
    "        res = []\n",
    "        k -= 1\n",
    "        for _ in range(ln):\n",
    "            res.append('7' if k & 1 else '4')\n",
    "            k >>= 1\n",
    "        return ''.join(reversed(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLuckyNumber(self, k: int) -> str:\n",
    "        def dfs(k):\n",
    "            if k == 1:\n",
    "                return \"4\";\n",
    "            elif k == 2:\n",
    "                return \"7\"\n",
    "\n",
    "            father = (k - 1) >> 1;\n",
    "            if k == (father << 1) + 1:\n",
    "                return dfs(father) + \"4\"\n",
    "            else:\n",
    "                return dfs(father) + \"7\"\n",
    "        \n",
    "        return dfs(k)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
